#include "StdAfx.h"

GeneticAlgorithm::GeneticAlgorithm(double crossRate, double mutRate, int popSize, int genSize, int genomeSize, bool elitism)
{
	this->crossoverRate = crossRate;
    this->mutationRate = mutRate;
    this->popSize = popSize;
    this->generationSize = genSize;
    this->genomeSize = genomeSize;
    this->totalFitness = 0;
	this->useElitism = elitism;
}

GeneticAlgorithm::~GeneticAlgorithm(void) { }

void GeneticAlgorithm::Evolve()
{
	int geration = 0;

	//create genomes
    for (int i = 0; i < this->popSize; i++)
		this->nextGeneration.push_back( new Genome(this->genomeSize, true, this->mutationRate) );

    do
    {
        RankPopulation();
        CreateNextGeneration(geration);
     }
     while (++geration < this->generationSize);
}

void GeneticAlgorithm::RankPopulation()
{
    this->totalFitness = 0.0;
	int i;
	//apply fitness function
    for (i=0; i<this->popSize; i++) { 
        this->nextGeneration[i]->Fitness = FitnessFunction(this->nextGeneration[i]);
		this->totalFitness += this->nextGeneration[i]->Fitness;
    }

    // create the new fitness table
    this->fitnessTable.clear();

	//standard deviation
	this->fitAvg = this->totalFitness / (double)this->popSize;
	this->fitStdDev =  0;
	double sum = 0;

	for(i=0; i < this->popSize; i++)
		sum += pow( (this->nextGeneration[i]->Fitness - this->fitAvg), 2);
	
	this->fitStdDev = sqrt( sum/(this->popSize - 1) );
	
	for(i=0; i < this->popSize; i++)
		this->fitnessTable.insert( pair<double, Genome*> (Max( (this->nextGeneration[i]->Fitness - (fitAvg - 2.0*fitStdDev)), 0 ), 
														  this->nextGeneration[i]) );
}

void GeneticAlgorithm::CreateNextGeneration(int t)
{
	srand((unsigned)time(NULL));
    Genome *parent1, *parent2, *child1, *child2;
            
    this->nextGeneration.clear();
	
	// create aux vectors to roullete selection
	this->_rsFitVals.clear();
	this->_rsGens.clear();

	multimap<double, Genome*>::iterator it;
	for(it=this->fitnessTable.begin(); it!=this->fitnessTable.end(); it++) {
		this->_rsFitVals.push_back((*it).first);
		this->_rsGens.push_back((*it).second);
	}

    //crossovers
    for (int i = 0; i < this->popSize; i += 2)
    { 
        parent1 = RouletteSelection();
        parent2 = RouletteSelection();
                
        if ( (rand() / (double)RAND_MAX) < this->crossoverRate)
            parent1->Crossover(parent2, child1, child2);
        else {
            child1 = parent1;
            child2 = parent2;
        }

        child1->Mutate(t, this->generationSize);
        child2->Mutate(t, this->generationSize);

        this->nextGeneration.push_back(child1);
        this->nextGeneration.push_back(child2);
    }

	//elitism
	if(this->useElitism)
		this->nextGeneration[0] = this->fitnessTable.end()->second;
}

Genome* GeneticAlgorithm::RouletteSelection()
{
	srand((unsigned)time(NULL));
    double randomFitness = (rand() / (double)RAND_MAX) * this->totalFitness;
    int idx = -1;
    int first = 0;
    int last = this->popSize - 1;
    int mid = (last - first) / 2;
    bool fim = false;

    // BinarySearch
    while ( (first <= last) && !fim )
    {
        if (randomFitness < this->_rsFitVals[mid])
            last = mid;
        else if (randomFitness > this->_rsFitVals[mid])
            first = mid;
        else
            fim = true;

        if (!fim) {
            if ((last - first) == 1) { //  lies between i and i+1
                idx = last;
                fim = true;
            }
            else
                mid = (first + last) / 2;
        }
        else
            idx = mid;
    }

    return this->_rsGens[idx];
}

double GeneticAlgorithm::FitnessFunction(Genome *g)
{
	BackTester bt;
	//bt.StartTest(quots, this->_btBegin, this->_btEnd, this->_systCfgBuilder(g, this->_systToOptim));
	return 0.;
}